﻿public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    /// <summary>
    /// 迭代法
    /// </summary>
    /// <param name="root"></param>
    /// <param name="targetSum"></param>
    /// <returns></returns>
    public IList<IList<int>> PathSum(TreeNode root, int targetSum)
    {
        // 先序遍历
        Stack<Tuple<TreeNode, int, IList<int>>> stack = new Stack<Tuple<TreeNode, int, IList<int>>>();
        IList<IList<int>> result = new List<IList<int>>();
        int sum = 0;
        IList<int> list;
        IList<int> list2;
        if (root is not null)
        {
            sum += root.val;
            list = new List<int>() { root.val };
            stack.Push(new Tuple<TreeNode, int, IList<int>>(root, sum, list));
        }

        Tuple<TreeNode, int, IList<int>> tuple;
        TreeNode node;
        while (stack.Count > 0)
        {
            tuple = stack.Pop();
            node = tuple.Item1;
            sum = tuple.Item2;
            list = tuple.Item3;

            if (node.left is null && node.right is null && targetSum == sum) result.Add(list);
            if (node.right is not null)
            {
                list2 = new List<int>(list);
                list2.Add(node.right.val);
                stack.Push(new Tuple<TreeNode, int, IList<int>>(node.right, sum + node.right.val, list2));
            }

            if (node.left is not null)
            {
                list2 = new List<int>(list);
                list2.Add(node.left.val);
                stack.Push(new Tuple<TreeNode, int, IList<int>>(node.left, sum + node.left.val, list2));
            }
        }

        return result;
    }
    
    /// <summary>
    /// 递归法
    /// </summary>
    /// <param name="root"></param>
    /// <param name="targetSum"></param>
    /// <returns></returns>
    public IList<IList<int>> PathSum2(TreeNode root, int targetSum)
    {
        IList<IList<int>> result = new List<IList<int>>();
        if (root is not null) GetPath(root, targetSum - root.val, result, new List<int>() { root.val });
        return result;
    }

    private void GetPath(TreeNode root, int targetSum, IList<IList<int>> result, List<int> list)
    {
        if (root is null) return;
        
        // 找到路径
        if (root.left is null && root.right is null && targetSum == 0)
        {
            list = new List<int>(list);
            result.Add(list);
        }

        if (root.left is not null)
        {
            list.Add(root.left.val);
            GetPath(root.left, targetSum - root.left.val, result, list);
            list.RemoveAt(list.Count - 1);
        }
        if (root.right is not null)
        {
            list.Add(root.right.val);
            GetPath(root.right, targetSum - root.right.val, result, list);
            list.RemoveAt(list.Count - 1);
        }
    }

    public static void Main(string[] args)
    {
        int?[] root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1];
        int targetSum = 22;
        TreeNode rootNode = CreateBinaryTree(root);
        Solution solution = new Solution();
        IList<IList<int>> result = solution.PathSum2(rootNode, targetSum);

        foreach (IList<int> res in result)
        {
            foreach (int r in res)
            {
                Console.Write($"{r} ");
            }
            Console.WriteLine();
        }
    }

    private static TreeNode CreateBinaryTree(int?[] root)
    {
        if (root is null || root.Length == 0 || root[0] is null)
        {
            return null;
        }

        Queue<TreeNode> queue = new Queue<TreeNode>();
        TreeNode rootNode = new TreeNode(root[0].Value);
        queue.Enqueue(rootNode);
        int i = 1;
        TreeNode node;

        while (i < root.Length && queue.Count > 0)
        {
            node = queue.Dequeue();
            if (root[i] is not null)
            {
                node.left = new TreeNode(root[i].Value);
                queue.Enqueue(node.left);
            }

            i++;
            if (i >= root.Length) break;
            if (root[i] is not null)
            {
                node.right = new TreeNode(root[i].Value);
                queue.Enqueue(node.right);
            }

            i++;
        }

        return rootNode;
    }
}